package linear;

public class ReorderList143 {
//    public static class LinkedListUtil.ListNode {
//        int val;
//        LinkedListUtil.ListNode next;
//
//        LinkedListUtil.ListNode(int x) {
//            val = x;
//        }
//    }

    public static void reorderList(LinkedListUtil.ListNode head) {
        if (head == null || head.next == null || head.next.next == null)
            return;
        LinkedListUtil.ListNode fast = head.next.next;
        LinkedListUtil.ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //fast == mid - 1 if length is odd == left-mid if length is even
        //now we need to reverse the right half of the list for later merge
        LinkedListUtil.ListNode prev = null;
        LinkedListUtil.ListNode cur = slow.next;

        while (cur != null) {
            LinkedListUtil.ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        LinkedListUtil.ListNode revHead = prev;
        slow.next = null;
        //now we have two linked list, we need to merge them in a zig-zag way
        LinkedListUtil.ListNode pLeft = head;
        LinkedListUtil.ListNode pRight = revHead;
        LinkedListUtil.ListNode tLeft = pLeft.next;
        LinkedListUtil.ListNode tRight = pRight.next;

        while (tLeft != null && tRight != null) {
            pLeft.next = pRight;
            pRight.next = tLeft;
            pLeft = tLeft;
            pRight = tRight;
            tLeft = pLeft.next;
            tRight = pRight.next;
        }
        pLeft.next = pRight;
    }

    public static void main(String[] args) {
        LinkedListUtil.ListNode head = new LinkedListUtil.ListNode(1);
        LinkedListUtil.ListNode cur = head;
        for (int i = 1; i < 4; i++) {
            cur.next = new LinkedListUtil.ListNode(i + 1);
            cur = cur.next;
        }
        reorderList(head);
        LinkedListUtil.printLinkedList(head);
//        printLinkedList();
    }
}
